約 221,383 件
https://w.atwiki.jp/akitaicpc/pages/50.html
vectorの使い方 vectorは一連の値を保存する動的配列です。配列のサイズは自動で確保されるのでメモリの心配はあまりする必要がありません。 vectorの宣言 std vector 格納したい変数の型名 変数名; vector 格納したい変数の型名 変数名; // using namespace std; を書いているとき コンストラクタ // T は格納したい型名 vector T v(); vector T v( size_type size ); // サイズ size のvectorを宣言 vector T v( size_type size , const T val ); // サイズ size のvectorを宣言し, すべての要素を val で初期化する. // (例) vector int v; // vectorのvを宣言 (サイズは0) vector int v(5); // 配列のサイズ5のvectorを宣言 vector int v(5, -1) // 配列のサイズ5のvectorを宣言し、各要素を-1で初期化する。 {-1, -1, -1, -1, -1} 使い方の一例 push_back(val) で 値 val を配列の末尾に追加できます。 pop_back() で配列の末尾の要素を削除できます。 普通の配列と同じように添字を指定して特定の要素を参照したり、特定の要素に代入したりできます。 // (例) v.push_back(5); // {} = {5} v.push_back(3); // {5} = {5, 3} v.push_back(1); // {5, 3} = {5, 3, 1} v.pop_back(); // {5, 3, 1} = {5, 3} v[1] = 2; // {5, 3} = {5, 2} よく使うメンバ関数 // vector T v, w;とします. // v と w が等しいときは true , そうでないときは false を返す. (戻り値 bool) v == w; // v と w を辞書順で比較して v の方が小さければ true , そうでないときは false を返す. (戻り値 bool) v w; // 要素数を返す. (戻り値 size_type) v.size(); // 要素をすべて削除する. (戻り値 void) v.clear(); // 要素数が 0 のときは true を, そうでないときは false を返す. (戻り値 bool) v.empty(); // 値 val を v の末尾に追加する. (戻り値 void) v.push_back( const T val ); // 末尾の要素を削除する. (戻り値 void) v.pop_back(); // pos の直前の位置に val を挿入して, その要素を指すイテレータを返す. (戻り値 iterator) v.insert( iterator pos , const T val ); // start から end までの要素を pos の直前に挿入する. (戻り値 void) v.insert( iterator pos, input_iterator start, input_iterator end ); // posの位置の要素を削除し, 削除された最終要素の直後を指すイテレータを返す. (戻り値 iterator) v.erase( iterator pos ); // v の先頭を指すイテレータを返す. (戻り値 iterator) v.begin(); // v の末尾を指すイテレータを返す. (戻り値 iterator) v.end(); その他 // vector の連結 // v = {1, 2, 3}, w = {4, 5, 6} v.insert( v.end() , w.begin() , w.end() ); // v = {1, 2, 3, 4, 5, 6} // vector の全要素の走査 for(int i = 0 ; i v.size() ; i++ ){ v[i]; } // vector の全要素の走査 (イテレータを使う) for(vector T iterator it = v.begin() ; it != v.end() ; ++it ){ *it; } // k 番目に値 val を追加 v.insert( v.begin() + k , T val ); // k 番目の要素を削除 v.erase( v.begin() + k ); ...
https://w.atwiki.jp/akitaicpc/pages/24.html
エイトクイーン問題 ...
https://w.atwiki.jp/akitaicpc/pages/217.html
setの使い方 setは集合を扱いたいときや重複せずに何かを数え上げたいときに使います. setの宣言 std set 格納したい型名 変数名; set 格納したい型名 変数名; // using namespace std; を書いているとき setでよく使うメンバ関数 // set T s; とします // 要素数を返す. (戻り値 size_type) s.size(); // 要素をすべて削除する (戻り値 void) s.clear(); // 要素数が 0 のときは true, そうでないときは false を返す. (戻り値 bool) s.empty(); // key に一致する要素の個数を返す. 要素は重複しないので必ず 0 か 1 が返ってくる. (戻り値 size_type) s.count( const T key ); // key を追加して, その要素を指すイテレータと挿入されたかどうかの組が返ってくる. (戻り値 pair iterator,bool ) s.insert( const T key ); // key を削除し, 削除した個数を返す. (戻り値 size_type) s.erase( const T key ); // s の先頭を指すイテレータを返す. (戻り値 iterator) s.begin(); // s の末尾を指すイテレータを返す. (戻り値 iterator) s.end(); その他 // すべての要素を走査する for(set T iterator it = s.begin() ; it != s.end() ; ++it ){ *it; } ...
https://w.atwiki.jp/akitaicpc/pages/19.html
C++に関する情報 STLについて STL(Standard Template Library 標準テンプレートライブラリ)とは,さまざまなオブジェクトを保存するコンテナと それにアクセスするためにつかう反復子(iterator イテレータ)、コンテナの内容を操作するためのアルゴリズムからなります。 コンテナには、vector,list,map,stack,queue,setなどたくさんあります。 このSTLには、スタック、キュー、リストなどのデータ構造がテンプレート化されているので、 STLを使うことで、基本的なデータ構造(リスト・スタック・キューなど)やアルゴリズム(ソートや値の検索など)を 自分で実装する必要がなくなるのでぜひSTLは使えるようになっておきましょう。 特にプログラミングコンテストだとstring, vector, map, set, stack, queue, priority_queueあたりをよく使います。 リファレンスはC++リファレンス(外部サイト)が役に立ちます。 stringの使い方 vectorの使い方 mapの使い方 setの使い方 stack,queue,priority_queueの使い方 dequeの使い方 listの使い方 bitsetの使い方 ...
https://w.atwiki.jp/akitaicpc/pages/80.html
最大値・最小値 C++では、 algorithm ヘッダをインクルードすることでmax(),min()関数が使えるので、 自分で書く必要はありません。max(),min()はよく使うので覚えておいてください。 引数の型は、int型でもdouble型でも使えます。 例) max( 12 , 35 ); //35が返ってくる min( -5.0 , 56.6 ); //-5.0が返ってくる 配列aから最大の値を返す関数 int array_max(int a[], int n){ int m = a[0]; for(int i=1 ; i n ; i++){ m = max( a[i] , m ); } return m; } 配列aから最小の値を返す関数 int array_mim(int a[], int n){ int m = a[0]; for(int i=1 ; i n ; i++){ m = min( a[i] , m ); } return m; } ...
https://w.atwiki.jp/akitaicpc/pages/32.html
文字列処理関数 string.h が必要となります。 メモリの中で特定の文字列を探す memchr(const *pbuf, int c, size_t MaxCount) 引数 pbuf 文字を探すメモリバッファのポインタ c 探す文字 MaxCount 文字数 戻り値 文字があればその文字のポインタ,なければNULL +プログラム例 #include stdio.h #include string.h int main(){ char pbuf[80]="Hello World!"; char c; int flag; printf("文字列 - %s \n",pbuf); printf("探したい１文字入力 "); scanf("%c", c); if( memchr( pbuf , c , strlen(pbuf) ) != NULL) printf("%sの中に%cは存在します \n" , pbuf , c); else printf("%sの中に%cは存在しません \n" , pbuf , c); return 0; } ２つの文字列を連結する strcat(char *dest, const char *source) 引数 dest 先頭の文字列 source 後ろに連結する文字列 戻り値 連結された後の文字列destのポインタ +プログラム例 #include stdio.h #include string.h int main(){ char str1[80] = "Hello"; char str2[] = "World!"; strcat(str1,str2); printf("%s \n", str1 ); } 実行結果 HelloWorld! 文字列の長さを求める strlen(const char *str) 引数 str 長さを求めたい文字列 戻り値 文字数 +プログラム例 #include stdio.h #include string.h int main(){ char str[80]; printf("文字列を入力してください "); scanf("%s", str); printf("入力した文字列の文字数は%dです \n", strlen(str) ); return 0; } ...
https://w.atwiki.jp/akitaicpc/pages/215.html
stringの使い方 string はSTLではありませんが、非常によく使うので覚えておきましょう。文字列を取り扱うときはC言語ではcharの配列を使うしかありませんでしたが, C++ではstringを使うのが便利です。 C言語の文字列(char配列)と同じように添字を指定して特定の文字を取得することができます。+演算子で文字列の連結ができ, 辞書順比較も比較演算子でできるので便利です。 stringの宣言 std string s; string s // using namespace std; を書いているとき コンストラクタ string s(); string s( size_type size , char c); // 長さ size の文字列を宣言し, 各文字をcで初期化する. よく使うメンバ関数 // string s; とします. // 文字列の長さを返す. (戻り値 size_type) s.size(); // 要素をすべて削除する. (戻り値 void) s.clear(); // 要素数が 0 のときは true を, そうでないときは false を返す. (戻り値 bool) s.empty(); // 文字 c を s の末尾に追加する. (戻り値 void) s.push_back( char c ); // 末尾の文字を削除する. (戻り値 void) s.pop_back(); // 位置 pos の直前の位置に文字列 str を挿入し, 挿入した後の文字列への参照を返す. (戻り値 basic_string ) s.insert( size_type pos , const string str ); // 位置 pos から num 文字削除する. num を省略すると位置 pos から最後までの文字を削除する. (戻り値 basic_string ) s.erase( size_type pos , size_type num = nops ); // 位置 pos 以降から文字列 strを検索し, 最初に見つかった位置を返す. (戻り値 size_type) s.find( const string str , size_type pos ) const; // 位置 pos から num 文字を文字列 str で置換する. (戻り値 basic_string ) s.replace( size_type pos , size_type num , const string str ); // 位置 pos から num 文字の部分文字列を返す. ただし文字列 s の値は変更されない. (戻り値 basic_string) s.substr( size_type pos = 0 , size_type num = npos ) const ; // C言語文字列の先頭ポインタを返す. (戻り値 const char*) s.c_str(); // s の先頭を指すイテレータを返す. (戻り値 iterator) s.begin(); // s の末尾を指すイテレータを返す. (戻り値 iterator) s.end(); その他 // 文字列の要素をすべて走査する for(int i=0 ; i s.size() ; i++ ){ s[i]; // s[i] は char } // 文字列 s の 文字列 before をすべて文字列 after に置き換える. void f(string s, const string before, const string after ){ int pos = 0; while( (pos = s.find( before )) != string npos ){ s.replace( pos , before.size() , after ); } } ...
https://w.atwiki.jp/akitaicpc/pages/20.html
ICPCの過去問題(国内予選・模擬国内予選) ここには過去のICPC国内予選の問題と模擬国内予選の問題を載せています。問題文は日本語のものしか載せていません。 難易度は★から★★★★★です。 ☆は★の半分(0.5)を表します。 ★(1.0-1.5) ・・・非常にやさしい、確実に解いてほしいレベル ★★(2.0-2.5) ・・・やさしい、国内予選突破するなら確実に解けないといけない ★★★(3.0-3.5) ・・・標準、この難易度の問題を一つは解かないと国内予選突破できないかもしれない ★★★★(4.0-4.5)・・・難しい、アジア地区予選で上位に食い込むにはこのレベルも解く力が必要となる ★★★★★(5.0) ・・・非常に難しい、上位のチームでも苦戦する難易度 難易度★★★までの問題を確実に解けないと国内予選突破はきびしいかもしれません 難易度は主観をかなり含んでいる可能性が高いのでICPC・JAG非公式難易度表を参考にするとよいです。 2013年 会津大会 問題 難易度 問題の種類 解答例 問題 A Integral Rectangles ★☆ 全探索 解答例 問題 B ICPC Ranking ★★ ソートするだけ 解答例 問題 C Hierarchical Democracy ★★★ 構文解析 解答例 問題 D Prime Caves ★★★ 素数列挙+DP 解答例 問題 E Anchored Balloon ★★★☆ 幾何 解答例 問題 F Rotate and Rewrite ★★★★ DP 解答例 2012年 東京大会 問題 難易度 問題の種類 解答例 問題 A Millennium ★ やるだけ 解答例 問題 B Recurring Decimals ★☆ 数列の計算 解答例 問題 C Biased Dice ★★☆ サイコロ 解答例 問題 D Railway Connection ★★★☆ ワーシャルフロイド 解答例 問題 E Chain-Confined Path ★★★★ 幾何・円と円の交点 解答例 問題 F Generic Poker ★★★★☆ ? 解答例 問題 G Patisserie ACM ★★★★☆ ? 解答例 2011年 福岡大会 問題 難易度 問題の種類 解答例 問題 A Chebyshev's Theorem ★ エラトステネスのふるい 解答例 問題 B The Balance of the World ★☆ 括弧の対応を調べる(スタック) 解答例 問題 C Identically Colored Panels Connection ★★☆ 再帰でDFS 解答例 問題 D And Then. How Many Are There? ★★★☆ 探索(DP) 解答例 問題 E Planning Rolling Blackouts ★★★★ DP 解答例 問題 F Watchdog Corporation ★★★★☆ 幾何 解答例 問題 G A Broken Door ★★★★☆ DP 解答例 2010年 東京大会 問題 難易度 問題の種類 解答例 問題 A Pablo Squarson's Headache ★ シミュレーション 解答例 問題 B Amazing Mazes ★★☆ BFS 解答例 問題 C Pollock's conjecture ★★☆ DP 解答例 問題 D Off Balance ★★★☆ 下から再帰で重心計算 解答例 問題 E The Most Powerful Spell ★★★★ ダイクストラ法 解答例 問題 F Old Memories ★★★★ 探索 解答例 問題 G Laser Beam Reflections ★★★★ 幾何 解答例 2009年 東京大会 問題 難易度 問題の種類 解答例 問題 A Next Mayor ★ シミュレーション 解答例 問題 B How Many Islands? ★☆ 再帰でDFS 解答例 問題 C Verbal Arithmetic ★★☆ 全探索 解答例 問題 D Discrete Speed ★★★☆ ダイクストラ法 解答例 問題 E Cards ★★★☆ 二部グラフの最大マッチング 解答例 問題 F Tighten Up! ★★★★☆ 幾何 解答例 2008年 会津大会 問題 難易度 問題の種類 解答例 問題 A Equal Total Scores ★ やるだけ 解答例 問題 B Monday-Saturday Prime Factors ★☆ エラトステネスのふるい 解答例 問題 C How can I satisfy thee? Let me count the ways... ★★☆ 構文解析 or 文字列置換 解答例 問題 D Twirling Robot ★★★ ダイクストラ法 解答例 問題 E Roll-A-Big-Ball ★★★☆ 幾何・線分と線分の距離 解答例 問題 F ICPC Intelligent Congruent Partition of Chocolate ★★★★☆ 探索 解答例 2007年 東京大会 問題 難易度 問題の種類 解答例 問題 A ICPC Score Totalizer Software ☆ やるだけ 解答例 問題 B Analyzing Login/Logout Records ★☆ やるだけ 解答例 問題 C Cut the Cake ★★☆ シミュレーション 解答例 問題 D Cliff Climbing ★★★ ダイクストラ法 解答例 問題 E Twirl Around ★★★★★ 幾何 解答例 問題 F Dr. Podboq or How We Became Asymmetric ★★★★ DP 解答例 2006年 横浜大会 問題 難易度 問題の種類 解答例 問題 A Dirichlet's Theorem on Arithmetic Progressions ★☆ エラトステネスのふるい 解答例 問題 B Organize Your Train part II ★★ 文字列操作 解答例 問題 C Hexerpents of Hexwamp ★★★★ 探索 解答例 問題 D Curling 2.0 ★★☆ 探索 解答例 問題 E The Genome Database of All Space Life ★★★★ 再帰/文字列操作 解答例 問題 F Secrets in Shadows ★★★★☆ 幾何・円と円の接線 解答例 2005年 東京大会 問題 難易度 問題の種類 解答例 問題 A Ohgas' Fortune ★ 利子の計算 解答例 問題 B Polygonal Line Search ★★☆ 幾何 解答例 問題 C Numeral System ★☆ 文字列操作 解答例 問題 D Traveling by Stagecoach ★★★☆ ダイクストラ法 解答例 問題 E Earth Observation with a Mobile Robot Team ★★★★☆ 幾何 解答例 問題 F Cleaning Robot ★★★ 探索 解答例 2004年 愛媛大会 問題 難易度 問題の種類 解答例 問題 A Hanafuda Shuffle ★ シミュレーション 解答例 問題 B Red and Black ★☆ 再帰でDFS 解答例 問題 C Unit Fraction Partition ★★☆ 探索 解答例 問題 D Circle and Points ★★★☆ 幾何 解答例 問題 E Water Tank ★★★★ シミュレーション 解答例 問題 F Name the Crossing ★★★★ ワーシャル-フロイド法 解答例 過去のICPCの模擬国内予選 ICPC OB/OGの会による模擬国内予選というものが毎年国内予選の前の6月あたりに開催されています。 難易度は国内予選想定でICPC国内予選と同じ環境でコンテストが開かれます。 ICPC OB/OGの会のページに問題文や解説や入出力データがあります。 2013年 模擬国内予選 問題 A King's Inspection ☆ やるだけ 解答例 問題 B Sim Forest 2013 ★★★ ソートするだけ 解答例 問題 C Twin book report ★★★☆ Greedy + DP 解答例 問題 D Sinking islands ★★★☆ 最小全域木 解答例 問題 E Ononokomachi's Edit War ★★★★ 構文解析 + ゲーム木探索 解答例 問題 F Princess Tetra's Puzzle ★★★★★ 二部グラフの最大マッチング 解答例 問題 G MirrorLabyrinth ★★★★☆ 幾何 + 最短路 解答例 2012年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Save Your Privacy! ★ やるだけ 解答例 問題 B You Are the Judge ★☆ ソートするだけ 解答例 問題 C Equation ★★★ 構文解析 or 文字列置換 解答例 問題 D Milky Way ★★★☆ 幾何 + 最短路 解答例 問題 E The Enemy of My Enemy is My Friend ★★★★ 枝刈り探索 or 半分全列挙 解答例 問題 F Dog Food ★★★★☆ 幾何：大変 解答例 問題 G Sister Ports ★★★★☆ ??? 解答例 2011年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A koukyoukoukokukikou ★ シミュレーション 解答例 問題 B Brave Force Story ★★ BFS(Brave Force StoryではなくBreadth First Search) 解答例 問題 C Fastest Route ★★★ bitDP 解答例 問題 D 6/2(1+2) ★★★☆ 構文解析 解答例 問題 E Divide the Cake ★★★☆ 幾何 解答例 問題 F Sakura Poetry ★★★★☆ ? 解答例 問題 G Intelligent Circular Perfect Cleaner ★★★★★ 幾何：大変 解答例 2010年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Sum of Consecutive Integers ★ 全探索 解答例 問題 B Moonlight Farm ★★ ソートするだけ 解答例 問題 C Differential Pulse Code Modulation ★★★ DP 解答例 問題 D Mr. Rito Post Office ★★★☆ ワーシャルフロイド法 + DP 解答例 問題 E Immortal Jewels ★★★☆ 幾何 解答例 問題 F Canal Water Going Up and Down ★★★★☆ シミュレーション 解答例 問題 G Magical Island 2 ★★★★★ 幾何 解答例 2009年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Luck Manipulator ★☆ やるだけ 解答例 問題 B Matsuzaki Number ★★ エラトステネスの篩 解答例 問題 C Brave Princess Revisited ★★★☆ ダイクストラ 解答例 問題 D Restrictive Filesystem ★★★☆ 区間管理 解答例 問題 E Mirror Cave ★★☆ BFS 解答例 問題 F Shore Erosion ★★★★★ 幾何 解答例 2008年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Princess's Gamble ★ やるだけ 解答例 問題 B Princess's Marriage ★☆ 貪欲法 解答例 問題 C Princess's Japanese ★★★★ 文字列処理 解答例 問題 D Princess in Danger ★★★ ダイクストラ法 解答例 問題 E Princess, a Cryptanalyst ★★★★ DP 解答例 問題 F Princess, a Strategist ★★★★ 幾何・線分同士の交差判定 解答例 2007年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Space Coconut Grab ★ 全探索 解答例 問題 B Osaki ★☆ シミュレーション 解答例 問題 C Surrounding Area ★★ DFSで塗りつぶし 解答例 問題 D Square Route ★★★ 数え上げ 解答例 問題 E Lifeguard in the Pool ★★★★☆ 幾何 解答例 問題 F Karakuri Doll ★★★★ 探索 解答例 2006年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Misterious Gems ★ シミュレーション 解答例 問題 B Amida, the City of Miracle ★☆ シミュレーション 解答例 問題 C X-Ray Screening System ★★★☆ 探索(DFS) 解答例 問題 D Railroad Conflict ★★★☆ 幾何：交点計算 解答例 問題 E Data Center on Fire ★★★★☆ ? 解答例 問題 F Water Pipe Construction ★★★ ワーシャルフロイド法 解答例 2005年 模擬国内予選 問題 難易度 問題の種類 解答例 問題 A Keitai Message ★☆ シミュレーション 解答例 問題 B Make Purse Light ★☆ 探索 解答例 問題 C Dragon Fantasy ★★★ 枝刈り探索 解答例 問題 D Area Separation ★★★☆ 幾何：交点計算 解答例 問題 E Poor Mail Forwarding ★★★★☆ ? 解答例 問題 F Gather the Maps! ★★★ DP 解答例 ...
https://w.atwiki.jp/akitaicpc/pages/15.html
その他・古典パズルなど ICPCのプログラミングに直接は役に立たないかもしれませんが、 息抜きにご利用ください。 古典パズルにはなかなか奥が深いものが多いので、これらでプログラミングをするのも楽しいかもしれません。 ※このページは未完成です Hello Worldをわかりにくくしてみた ８パズル? ３目並べ? 水の分配? 倉庫番パズル? ハノイの塔? エイトクイーン問題? ナイトツアー問題? どうでもいいページ ...
https://w.atwiki.jp/akitaicpc/pages/22.html
３目並べ ...